package main

import (
	"container/list"
	"fmt"
	"go-study/algorithm/standard"
)

// 如何查找到达目标词的最短链长度

func main() {
	D := list.New()
	strs := []string{"pooN", "pbcc", "zamc", "poIc", "pbca", "pbIc", "poIN"}
	for _, str := range strs {
		D.PushBack(str)
	}

	start := "TooN"
	target := strs[4]
	fmt.Println(shortestChainLen(start, target, D))
}

type qItem struct {
	word string
	len  int
}

func newQItem(word string, len int) *qItem {
	return &qItem{word, len}
}

// 判断两个字符串是否只有一个不同的字符
func isAdjacent(a, b string) bool {
	diff := 0
	for i, v := range a {
		if byte(v) != b[i] {
			diff++
		}
		if diff > 1 {
			return false
		}
	}
	if diff == 1 {
		return true
	} else {
		return false
	}
}

// 广度优先搜索
// 返回从 start 到 target 的最短链，D 是字典
func shortestChainLen(start, target string, D *list.List) int {
	// 新建队列
	Q := standard.NewSliceQueue()
	Q.EnQueue(newQItem(start, 1))

	for !Q.IsEmpty() {
		// 从队列中取出一个元素
		cur := Q.DeQueue().(*qItem)

		// 遍历字典中未取走的元素
		for e := D.Front(); e != nil; e = e.Next() {
			// 获取字典值
			tmp := e.Value.(string)
			// 如果两个元素只有一个字符不同
			if isAdjacent(cur.word, tmp) {
				// 将元素从字典移入到队列中
				Q.EnQueue(newQItem(tmp, cur.len+1))
				D.Remove(e)

				// 如果得到了目标字符
				if tmp == target {
					return cur.len + 1
				}
			}
		}
	}

	return -1
}
